package com.dlut.java;


class Solution {
    public static void main(String[] args) {
        int[] arr = {0, -3, -3, 1, 1, 2};
        Solution s = new Solution();
        int sum = s.countRangeSum(arr, 3, 5);
        System.out.println(sum);
    }

    /**
     * 力扣 327
     * 给你一个整数数组nums 以及两个整数lower 和 upper 。
     * 求数组中，值位于范围 [lower, upper]（包含lower和upper）之内的 区间和的个数 。
     * 前缀和 + 归并排序 + 滑动窗口
     */
    public int countRangeSum(int[] nums, int lower, int upper) {
        long s = 0;
        long[] sum = new long[nums.length + 1];
        for (int i = 0; i < nums.length; ++i) {
            s += nums[i];
            sum[i + 1] = s;
        }
        return countRangeSumRecursive(sum, lower, upper, 0, sum.length - 1);
    }

    public int countRangeSumRecursive(long[] sum, int lower, int upper, int left, int right) {
        if (left >= right)
            return 0;
        int mid = left + (right - left) / 2;
        int num1 = countRangeSumRecursive(sum, lower, upper, left, mid);
        int num2 = countRangeSumRecursive(sum, lower, upper, mid + 1, right);
        int num3 = merge(sum, lower, upper, left, mid, right);

        return num1 + num2 + num3;
    }

    public int merge(long[] sum, int lower, int upper, int left, int mid, int right){
        int count = 0;
        int p1 = left, p2 = mid + 1, i = 0;
        int p11 = p1, p12 = p1;
        for (int j = mid + 1; j <= right; j++) {
            while (p11 <= mid && sum[p11] < sum[j] - upper){
                p11 ++;
            }
            while (p12 <= mid && sum[p12] <= sum[j] - lower){
                p12 ++;
            }
            count += p12 - p11;
        }

        long[] help = new long[right - left + 1];
        while (p1 <= mid && p2 <= right){
            help[i++] = sum[p1] <= sum[p2] ? sum[p1++] : sum[p2++];
        }
        while (p1 <= mid){
            help[i++] = sum[p1++];
        }
        while (p2 <= right){
            help[i++] = sum[p2++];
        }
        System.arraycopy(help, 0, sum, left, help.length);
        return count;
    }
}

